#include <bits/stdc++.h>

const int n = 200000;
int data[n + 5];

// 生成随机数据,保存在文件finame中
void creatData(const char* finame, int count, int range = 100) {
  // 生成随机数据，将数据保存在指定文件中
  freopen(finame, "w", stdout);  // 将标准输出流重定向到文件“in.txt”
  srand(time(0));                // 使用当前时间作为随机数种子
  for (int i = 0; i < count; i++) {
    printf("%d ", rand() % range + 1);  // 随机保存到文件“in.txt”中
  }
  fclose(stdout);
}
// 读取文件中的数据到数组
void readData(const char* finame, int data[], int count) {
  freopen(finame, "r", stdin);
  for (int i = 0; i < count; i++) {
    scanf("%d", &data[i]);
  }
  fclose(stdin);
}
// 输出排序后的结果到文件
void writeData(const char* finame, int data[], int count) {
  freopen(
      finame, "a",
      stdout);  // 追加到一个文件。写操作向文件末尾追加数据。如果文件不存在，则创建文件。
  for (int i = 0; i < count; i++) {
    printf("%d ", data[i]);
  }
  fclose(stdout);
}
// 输出排序后的结果到文件（带有运行时间）
void writeData(const char* finame, int data[], int count, int begin, int end) {
  freopen(finame, "w", stdout);
  int time = (end - begin) / CLOCKS_PER_SEC;
  printf("begin:%d \nend:%d \ntime:%ds \n", begin, end, time);
  fclose(stdout);
  writeData(finame, data, count);
}
// 输出统计结果
void statistics(const char* sortMethodName, const int count, const int begin,
                const int end) {
  freopen("statistics.txt", "a", stdout);
  int time = (end - begin) / CLOCKS_PER_SEC;
  // printf("sortMethodName=%s, count=%d, beging=%d, end=%d, time=%ds\n",
  //        sortMethodName, count, begin, end, time);
  printf("%s\t\t%d\t\t%d\t\t%d\t\t%ds\n", sortMethodName, count, begin, end,
         time);
  fclose(stdout);
}
// 交换两个元素
void swap(int& a, int& b) {
  int t = a;
  a = b;
  b = t;
}
// 1、冒泡排序
void bubbleSort(int data[], int n) {
  for (int i = 0; i < n; i++) {
    bool flag = true;
    for (int j = 0; j < n - i - 1; j++) {
      if (data[j] > data[j + 1]) {
        swap(data[j], data[j + 1]);
        flag = false;
      }
    }
    if (flag) break;  // 若已经有序，则提前结束循环
    // todo...继续改进，跳过已经有序的部分
  }
}
// 2、选择排序
void selectSort(int data[], int n) {
  int mini;
  for (int i = 0; i < n - 1; i++) {
    mini = i;
    for (int j = i + 1; j < n; j++) {
      if (data[j] < data[mini]) mini = j;
    }
    if (mini != i) {
      swap(data[i], data[mini]);
    }
  }
}
// 3、插入排序
void insertSort(int data[], int n) {
  int i, j, temp;
  for (i = 1; i < n; i++) {
    j = i;
    temp = data[j];
    while (j > 0 && temp < data[j - 1]) {  // 寻找插入位置，元素依次往后挪
      data[j] = data[j - 1];
      --j;
    }
    // 此时j即元素temp应该插入的位置
    data[j] = temp;
  }
}
// 4、希尔排序
void shellSort(int data[], int n) {
  int i, j, gap, temp;
  // 进行分组，最开始时的增量（gap）为数组长度的一半
  for (gap = n / 2; gap > 0; gap /= 2) {
    // 对各个分组进行排序（自己选择排序方式）
    for (i = gap; i < n; i++) {
      // 此处采用的是插入排序（移动法，相比交换法能减少交换次数）
      j = i;
      temp = data[j];
      while (j > gap && temp < data[j - gap]) {  // 寻找插入位置，元素依次往后挪
        // 注意循环条件，防止数组越界
        data[j] = data[j - gap];
        j -= gap;
      }
      // 此时j即元素temp应该插入的位置
      data[j] = temp;
    }
  }
}
// 5、快速排序
void quickSort(int data[], int left, int right)  //快速排序
{
  if (left < right) {
    // Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1

    int i = left, j = right, x = data[left];
    while (i < j) {
      while (i < j && data[j] >= x)  // 从右向左找第一个小于x的数
        j--;
      if (i < j) data[i++] = data[j];

      while (i < j && data[i] < x)  // 从左向右找第一个大于等于x的数
        i++;
      if (i < j) data[j--] = data[i];
    }
    data[i] = x;
    quickSort(data, left, i - 1);  // 递归调用
    quickSort(data, i + 1, right);
  }
}

// 6、堆排序
void adjust(int* a, int i, int n) {
  // 调整堆
  int temp = a[i];
  for (int k = 2 * i + 1; k < n; k = k * 2 + 1) {
    if (k + 1 < n && a[k] < a[k + 1]) {  // 如果左孩子小于右孩子，j指向右孩子
      k++;
    }
    if (a[k] > temp) {  // 如果子节点大于有节点，将子节点的值赋值给父节点
      a[i] = a[k];
      i = k;
    } else {
      break;
    }
  }
  a[i] = temp;
}
void heapSort(int* a, int n) {
  // 构建大顶堆
  for (int i = n / 2 - 1; i >= 0; i--) {
    adjust(a, i, n);
  }
  for (int i = n - 1; i > 0; --i) {
    swap(a[0], a[i]);
    adjust(a, 0, i);
  }
}

int main() {
  creatData("test.txt", n, RAND_MAX);  // 生成范围为1-100随机数据
  int begin;
  int end;
  // 1、冒泡排序
  readData("test.txt", data, n);
  begin = clock();
  bubbleSort(data, n);
  end = clock();
  writeData("out_bubbleSort.txt", data, n, begin, end);  // 输出结果到文件
  statistics("bubbleSort", n, begin, end);               // 记录统计信息

  // 2、选择排序
  readData("test.txt", data, n);
  begin = clock();
  selectSort(data, n);
  end = clock();
  writeData("out_selectSort.txt", data, n, begin, end);  // 输出结果到文件
  statistics("selectSort", n, begin, end);               // 记录统计信息

  // 3、插入排序
  readData("test.txt", data, n);
  begin = clock();
  insertSort(data, n);
  end = clock();
  writeData("out_insertSort.txt", data, n, begin, end);  // 输出结果到文件
  statistics("insertSort", n, begin, end);               // 记录统计信息

  // // 4、希尔排序
  readData("test.txt", data, n);
  begin = clock();
  shellSort(data, n);
  end = clock();
  writeData("out_shellSort.txt", data, n, begin, end);  // 输出结果到文件
  statistics("shellSort", n, begin, end);               // 记录统计信息

  // 5、快速排序
  readData("test.txt", data, n);
  begin = clock();
  quickSort(data, 0, n - 1);
  end = clock();
  writeData("out_quickSort.txt", data, n, begin, end);  // 输出结果到文件
  statistics("quickSort", n, begin, end);               // 记录统计信息

  // 6、堆排序
  readData("test.txt", data, n);
  begin = clock();
  heapSort(data, n);
  end = clock();
  writeData("out_heapSort.txt", data, n, begin, end);  // 输出结果到文件
  statistics("heapSort", n, begin, end);               // 记录统计信息

  printf("排序完成，打开文件查看结果！\n");
  return 0;
}
